#include <stdio.h>
#include <stdlib.h>

//自定义动态数组结构
typedef struct
{
    int *data;//指向堆区的内存(数组)
    size_t size;//有效元素的个数
    size_t capacity;//可容纳的最大元素个数
}DynamicArr;

//初始化动态数组
void initArr(DynamicArr *arr,size_t initialCapacity);
//释放动态数组
void destoryArr(DynamicArr *arr);
//在指定位置插入元素
void insertAt(DynamicArr *arr,size_t index,int element);
//在结尾处插入元素
void insertEnd(DynamicArr *arr,int element);
/**
 * @brief 删除指定位置的元素
 * @param arr 指向自定义DynamicArr结构体变量的指针
 * @param index 要删除元素的下标
 * @return 无
 */
void removeAt(DynamicArr *arr,size_t index);
//对数组进行升序排序
void ascSort(DynamicArr *arr);
//输出动态数组元素
void showArr(DynamicArr *arr);

//扩容操作
static void resizeArr(DynamicArr *arr,size_t newCapacity);

int main(void)
{
    DynamicArr arry;
    initArr(&arry,2);
    //插入元素
    insertAt(&arry,0,45);
    insertAt(&arry,1,62);
    //printf("size:%ld\n",arry.size);
    //printf("capacity:%ld\n",arry.capacity);
    //扩容后插入
    //insertAt(&arry,2,3);
    //printf("size:%ld\n",arry.size);
    //printf("capacity:%ld\n",arry.capacity);
    //insertAt(&arry,1,666);
    //insertEnd(&arry,999);
    insertEnd(&arry,15);
    insertEnd(&arry,78);
    insertEnd(&arry,30);
    showArr(&arry);
    ascSort(&arry);
    showArr(&arry);

    destoryArr(&arry);
    return 0;
}

void initArr(DynamicArr *arr,size_t initialCapacity)
{
    //初始化有效元素个数
    arr->size=0;
    //初始化容量大小
    arr->capacity=initialCapacity;
    //动态分配内存
    arr->data=malloc(sizeof(int)*initialCapacity);
}

void destoryArr(DynamicArr *arr)
{
    arr->size=0;
    arr->capacity=0;
    free(arr->data);
    arr->data=NULL;//设置空值，防止野指针
}

void insertAt(DynamicArr *arr,size_t index,int element)
{
    //插入位置验证
    if(index>arr->size)
    {
        printf("插入位置无效\n");
        return;
    }
    //判断是否需要扩容
    if(arr->size>=arr->capacity)
    {
        //需要扩容
        //arr->capacity*2
        //to do:扩容
        resizeArr(arr,arr->capacity*2);
    }
    //插入新元素
    //要先让旧元素移动位置
    for(size_t i=arr->size;i>index;i--)
    {
        //元素后移，腾出位置
        arr->data[i]=arr->data[i-1];
    }
    //在指定位置插入元素
    arr->data[index]=element;
    //最后更新有效元素的个数
    arr->size++;
}

void insertEnd(DynamicArr *arr,int element)
{
    //内部计算出尾部元素位置
    insertAt(arr,arr->size,element);
}

//void removeAt(DynamicArr,size_t index)
//{
    
//}

void ascSort(DynamicArr *arr)
{
    int temp=0;
    //使用冒泡排序
    for(size_t i=0;i<arr->size-1;i++)
    {
        for(size_t j=0;j<arr->size-1-i;j++)
        {
            //若当前元素比相邻的后方元素大
            if(arr->data[j]>arr->data[j+1])
            {
                temp=arr->data[j];
                arr->data[j]=arr->data[j+1];
                arr->data[j+1]=temp;
            }
        }
    }
}

void showArr(DynamicArr *arr)
{
    for(size_t i=0;i<arr->size;i++)
    {
        printf("%d ",arr->data[i]);
    }
    printf("\n");
}

static void resizeArr(DynamicArr *arr,size_t newCapacity)
{
    arr->capacity=newCapacity;
    arr->data=(int *)realloc(arr->data,sizeof(int)*newCapacity);
}